#include "common.h"

vector<string> ans;
int flg[17];
int nn;
int ln, rn;
void dfs(string t)
{
	if (t.size() == 2 * nn)
	{
		ans.push_back(t);
		return;
	}
	if (ln < nn)
	{
		t.push_back('(');
		ln++;
		dfs(t);
		t.pop_back();
		ln--;
	}
	if (rn < nn && rn < ln)
	{
		t.push_back(')');
		rn++;
		dfs(t);
		t.pop_back();
		rn--;
	}
}
vector<string> generateParenthesis(int n)
{
	nn = n;
	dfs("");
	return ans;
}